/*
Source : https://leetcode.com/problems/coin-change/
Author : nflush@outlook.com
Date   : 2016-07-15
*/

/*
322. Coin Change
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 28146
?Total Submissions: 111126
?Difficulty: Medium



You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. 

Example 1:
 coins = [1, 2, 5], amount = 11
 return 3 (11 = 5 + 5 + 1) 

Example 2:
 coins = [2], amount = 3
 return -1. 

Note:
 You may assume that you have an infinite number of each kind of coin. 

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.



Subscribe to see which companies asked this question
*/

// TLE
class Solution {
private:
    static bool compare(const int a, const int b){
        return a > b;
    }
    int coinChangeIn(vector<int>& coins, int amount, int pos){
        if (amount == 0) return 0;
        if (pos >= coins.size()) return -1;
        int cast = coins[pos];
        int ret = amount +1;
        for (int i = amount/cast; i >= 0; i--){
            int x= coinChangeIn(coins, amount - cast * i, pos+1);
            if (x != -1){
                ret = min(ret, i + x);
            }
        }
        return ret == amount + 1 ? -1: ret;
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        std::sort(coins.begin(), coins.end(), compare);
        
        return coinChangeIn(coins, amount, 0);
    }
};

// DP
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        const int MAX = amount +1;
        vector<int> dp(amount+1, MAX);
        dp[0]=0;
        
        for(int i=1; i<=amount; i++) {
            for (int j=0; j<coins.size(); j++){
                if (i >= coins[j]) {
                    dp[i] = min( dp[i], dp[i-coins[j]] + 1 );
                }
            }
        }

        return dp[amount]==MAX ? -1 : dp[amount];
    }
};

